package bishi.day29_5_27;

/**
 * 求正数数组的最小不可组成和
 * 动态规划
 * @author 是阿秋啊
 * @date 2022/06/01 15:08
 **/
public class Solution {
    /**
     *	正数数组中的最小不可组成和
     *	输入：正数数组arr
     *	返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i : arr) {
            min = Math.min(min,i);
            max+=i;
        }
        boolean[] ret = new boolean[max + 1];
        ret[0] = true;
        for (int i : arr) {
            for (int j = max; j >= i ; j--) {
                ret[j] = ret[j - i] || ret[j];
            }
        }
        for (int i = min; i < ret.length; i++) {
            if (!ret[i]) {
                return i;
            }
        }
        return max + 1;
    }
}
